Problems tagged with "binary search trees"
Problem #161
Tags: binary search trees
True or False: the below is a binary search tree.
Solution
False. 24 is in the left subtree of 23, but 24 > 23. (It is also in the left subtree of 34, which is fine, but every node in 23's left subtree must be less than 23.)
Problem #162
Tags: binary search trees
Consider the following binary search tree:
How many comparisons does it take to query 3? That is, how many times is 3 compared to another number during a query?
Solution
Answer: 4. The query compares 3 to 54, then 50, then 16, then 5. Since 5 has no left child, the query ends there and reports that 3 is not in the tree.
Problem #163
Tags: binary search trees
Consider the following binary search tree:
Where should we insert 49 ?
Solution
The right edge of 34. Starting at the root: 49 < 54, so go left to 50; 49 < 50, so go left to 16; 49 > 16, so go right to 34; 49 > 34, and 34 has no right child, so 49 becomes the right child of 34.
Problem #164
Tags: binary search trees
Draw the binary search tree that results from inserting the following nodes into an initially empty tree, in the order given: 5, 3, 1, 8, 4, 2, 6.
Solution
Problem #165
Tags: binary search trees
Suppose the numbers 41, 32, and 40 are inserted (in that order) into the below binary search tree. Draw where the new nodes will appear.
Solution
41 will be the right child of 33.
32 will be the right child of 31.
40 will be the left child of 41.
Problem #166
Tags: binary search trees
Suppose the numbers 41, 32, and 33 are inserted (in that order) into the below binary search tree. Draw where the new nodes will appear.
Solution
41 will become the left child of 46.
32 will become the left child of 35.
33 will become the right child of 32.
Problem #167
Tags: binary search trees
Define the largest gap in a collection of numbers (also known as its range) to be greatest difference between two elements in the collection (in absolute value). For example, the largest gap in \(\{4, 9, 5, 1, 6\}\) is 8 (between 1 and 9).
Suppose a collection of \(n\) numbers is stored in a balanced binary search tree. What is the time complexity required of an efficient algorithm to calculate the largest gap in the collection? State your answer as a function of \(n\) in asymptotic notation.
Solution
\(\Theta(\log n)\). To find the largest gap, we simply need to find the minimum and the maximum in the balanced BST, which both take \(\Theta(\log{n})\) time. Therefore adding them up, the time complexity for calculating the largest gap is \(\Theta(\log{n})\).
Problem #168
Tags: binary search trees
Define the largest gap in a collection of numbers to be the largest difference between two distinct elements in the collection (in absolute value). For example, the largest gap in \(\{4, 9, 1, 6\}\) is 8 (between 1 and 9).
Suppose a collection of \(n\) numbers is stored in a balanced binary search tree. What is the time complexity required for an efficient algorithm to calculate the largest gap of the numbers in the BST? State your answer as a function of \(n\) in asymptotic notation.
Solution
\(\Theta(\log n)\). With the same reasoning as Problem 20, we only require the largest and smallest number in the BST in order to find the largest gap (just subtract the smallest from the largest number), therefore the time complexity of this operation in a balanced BST will be \(\Theta(\log{n})\).
Problem #169
Tags: binary search trees
Suppose a collection of \(n\) numbers is stored in a balanced binary search tree. What is the time complexity required of an efficient algorithm to calculate the mean of the collection? State your answer as a function of \(n\) in asymptotic notation.
Solution
\(\Theta(n)\). Without knowing any information on the numbers, the best we can do to compute the mean is to add all numbers in the BST divided by the total number of nodes in the BST. To do this, we will have to traverse the entire BST no matter what (via some traversal algorithm), which takes \(\Theta(n)\) time. (Note that the word \(\textbf{balanced}\) does not help in this question!!!)
Problem #170
Tags: binary search trees
Define the smallest gap in a collection of numbers to be the smallest difference between two distinct elements in the collection (in absolute value). For example, the smallest gap in \(\{4, 9, 1, 6\}\) is 2 (between 4 and 6).
Suppose a collection of \(n\) numbers is stored in a balanced binary search tree. What is the time complexity required for an efficient algorithm to calculate the smallest gap of the numbers in the BST? State your answer as a function of \(n\) in asymptotic notation.
Solution
\(\Theta(n)\). The smallest gap in the BST can occur between any two consecutive pairs of numbers in the BST, meaning that no matter what we need to search through the whole tree to obtain this number, taking \(\Theta(n)\) time.
Problem #171
Tags: binary search trees
Consider the following .insert() method for a binary search tree:
def insert(self, new_key):
# assume new_key is unique
current_node = self.root
parent = None
# find place to insert the new node
while current_node is not None:
parent = current_node
if current_node.key < new_key:
current_node = current_node.right
else: # current_node.key > new_key
current_node = current_node.left
# create the new node
new_node = Node(key=new_key, parent=parent)
# if parent is None, this is the root. Otherwise, update the
# parent's left or right child as appropriate
if parent is None:
self.root = new_node
elif parent.key < new_key:
parent.right = new_node
else:
parent.left = new_nodeLet's say we want to insert a new number \(x\) into a binary search tree.Define height_left as the height of the left half of the binary tree (the root and everything to the left of it), and height_right as the height of the right side. For this problem, measure height as the number of nodes on the longest path starting at the root (so a tree consisting of only a root has height 1). Let height_left be greater than height_right. In the worst case, how many iterations of the while loop of .insert() will need to be completed?
Solution
height_left. Each iteration of the while loop moves one level down the tree, visiting one node. In the worst case, \(x\) is inserted below the deepest node, which is on the left side since height_left is greater than height_right. The loop visits every node on the path from the root to that node, which is height_left nodes.
Problem #172
Tags: binary search trees
Suppose bst is a binary search tree with \(n\) nodes constructed in the following way:
bst = BinarySearchTree()
for i in range(n):
if i % 2 == 0:
bst.insert(i)What is the time complexity of the following code?
for i in range(n):
bst.query(i)Solution
\(\Theta(n^2)\). The keys \(0, 2, 4, \ldots\) are inserted in increasing order, so each new node becomes the right child of the previous one and the tree is a "linked list" of height \(\Theta(n)\). Querying \(i\) walks down this chain past about \(i/2\) nodes, so the total time is \(\sum_{i=0}^{n-1} \Theta(i) = \Theta(n^2)\).
Problem #173
Tags: time complexity, binary search trees
Suppose a collection of unique numbers is stored in a balanced binary search tree, and that each node in the tree has been given a .size attribute which contains the number of nodes in the subtree rooted at that node. What is the time complexity required of an efficient algorithm for computing the number of elements in the collection which are larger than some threshold, \(t\)?
Solution
\(\Theta(\log{n})\). We can consider the following algorithm: Query for \(t\) in the BST, and define a new variable total for tracking the result. For each step of the recursion, if we go to the left, add the size of the right branch + 1 to the running total. We repeat the above until the query() function finishes running, which will give us exactly the number of elements in the collection which are larger than \(t\). Since we are querying (and adding some constant time updating steps) in a balanced BST, the time complexity for this question will be \(\Theta(\log{n})\).
Problem #187
Tags: hashing, binary search trees
Suppose you need to keep track of a large dynamic collection of numbers. You will be performing n insertions, n deletions, and a very small number of queries for the maximum element in the collection. You will also be performing membership queries.
Which data structure should you use? You may assume that time complexity is the most important criterion.
Solution
A hash table. In a hash table, insertions and deletions take constant time (on average), while a query for the maximum element takes \(\Theta(n)\). Since we are running only a constant number of max queries, they take \(\Theta(n)\) time in total, and the \(n\) insertions and \(n\) deletions also take \(\Theta(n)\) time in total. In a balanced BST, all of these operations take \(\Theta(\log n)\), which means running n insertions and deletions will be \(\Theta(n \log n)\) -- slower than a hash table.
Problem #188
Tags: hashing, binary search trees
Suppose you need to keep track of a large dynamic collection of numbers. The three most common operations you will be performing are insertions, deletions, and queries for the maximum element in the collection. You may assume that the number of maximum queries you will be making is close to the number of insertions/deletions. You will also be performing membership queries.
Which data structure should you use? You may assume that time complexity is the most important criterion.
Solution
A self-balancing binary search tree. The key is that we're allowing deletions and max queries. If we delete the maximum, we'll need to find the next maximum upon our next query. In a hash table and unsorted array, this will take linear time. In a sorted array, finding the next max takes constant time -- but insertion and deletion potentially take linear time. In a balanced BST, all of these operations take \(\Theta(\log n)\) in the worst case -- this is because a BST essentially keeps nodes in sorted order.